{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distribute Candies to People"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distributeCandies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分糖果 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>排排坐，分糖果。</p>\n",
    "\n",
    "<p>我们买了一些糖果 <code>candies</code>，打算把它们分给排好队的 <strong><code>n = num_people</code></strong> 个小朋友。</p>\n",
    "\n",
    "<p>给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 <code>n</code>&nbsp;颗糖果。</p>\n",
    "\n",
    "<p>然后，我们再回到队伍的起点，给第一个小朋友 <code>n&nbsp;+ 1</code> 颗糖果，第二个小朋友 <code>n&nbsp;+ 2</code> 颗，依此类推，直到给最后一个小朋友 <code>2 * n</code>&nbsp;颗糖果。</p>\n",
    "\n",
    "<p>重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。</p>\n",
    "\n",
    "<p>返回一个长度为 <code>num_people</code>、元素之和为 <code>candies</code> 的数组，以表示糖果的最终分发情况（即 <code>ans[i]</code> 表示第 <code>i</code> 个小朋友分到的糖果数）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>candies = 7, num_people = 4\n",
    "<strong>输出：</strong>[1,2,3,1]\n",
    "<strong>解释：</strong>\n",
    "第一次，ans[0] += 1，数组变为 [1,0,0,0]。\n",
    "第二次，ans[1] += 2，数组变为 [1,2,0,0]。\n",
    "第三次，ans[2] += 3，数组变为 [1,2,3,0]。\n",
    "第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>candies = 10, num_people = 3\n",
    "<strong>输出：</strong>[5,2,3]\n",
    "<strong>解释：</strong>\n",
    "第一次，ans[0] += 1，数组变为 [1,0,0]。\n",
    "第二次，ans[1] += 2，数组变为 [1,2,0]。\n",
    "第三次，ans[2] += 3，数组变为 [1,2,3]。\n",
    "第四次，ans[0] += 4，最终数组变为 [5,2,3]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= candies &lt;= 10^9</code></li>\n",
    "\t<li><code>1 &lt;= num_people &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distribute-candies-to-people](https://leetcode.cn/problems/distribute-candies-to-people/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distribute-candies-to-people](https://leetcode.cn/problems/distribute-candies-to-people/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n4', '10\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if limit > n:\n",
    "            return math.comb(n+2, 2)\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k == 0:\n",
    "                return min(i, limit) - max(0, i - limit) + 1\n",
    "            \n",
    "            ans = 0\n",
    "            for j in reversed(range(limit+1)):\n",
    "                if i - j > 2 * limit: break\n",
    "                ans += dp(i - j, k - 1)\n",
    "            return ans\n",
    "        \n",
    "        return dp(n, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n+1):\n",
    "            for j in range(n+1):\n",
    "                k = n - i - j\n",
    "                if k >= 0 and i <= limit and j <= limit and k <= limit:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(limit+1):\n",
    "            for j in range(limit+1):\n",
    "                for k in range(limit+1):\n",
    "                    if i+j+k == n:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\r\n",
    "        return self.solve2(n, limit)\r\n",
    "    \"\"\"\r\n",
    "        1. Brute Force\r\n",
    "    \"\"\"\r\n",
    "    def solve1(self, n: int, limit: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(limit+1):\r\n",
    "            for j in range(limit+1):\r\n",
    "                k = n - i - j\r\n",
    "                if k >= 0 and k <= limit:\r\n",
    "                    ans += 1\r\n",
    "        return ans\r\n",
    "    \"\"\"\r\n",
    "        2. 排容原理\r\n",
    "        a. 所有方案數：\r\n",
    "            H(3, n) = C(n+2, n) = C(n+2, 2)\r\n",
    "        b. 至少一人拿到超過 limit 個糖果的方案數：\r\n",
    "            (先分(limit+1)給他，剩下的分給所有人)\r\n",
    "            3 * H(3, n-(limit+1)) = 3 * C(n−(limit+1)+2, 2)\r\n",
    "        c. 至少兩人拿到超過 limit 個糖果的方案數：\r\n",
    "            3 * C(n−2⋅(limit+1)+2, 2)\r\n",
    "    \"\"\"\r\n",
    "\r\n",
    "    def solve2(self, n: int, limit: int) -> int:\r\n",
    "        if n > 3 * limit: # 三人都拿到超過 limit 個糖果，沒有方案\r\n",
    "            return 0\r\n",
    "        ans = comb(n + 2, 2)\r\n",
    "        if n >= (limit + 1): # 至少一人拿到超過 limit 個糖果\r\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\r\n",
    "        if n >= 2 * (limit + 1): # 至少兩人拿到超過 limit 個糖果\r\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        @cache\n",
    "        def f(i,n):\n",
    "            if i==2 or n<0:\n",
    "                if n>=0 and n<=limit:\n",
    "                    return 1\n",
    "                return 0\n",
    "            m=0\n",
    "            for j in range(limit+1):\n",
    "                m+=f(i+1,n-j)\n",
    "            return m\n",
    "        return f(0,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(0, min(n, limit)+1):\n",
    "            ans += max(0, min(limit, n - i) - max(0, n - i - limit) + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n):\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\r\n",
    "        return self.solve2(n, limit)\r\n",
    "    \"\"\"\r\n",
    "        1. Brute Force\r\n",
    "    \"\"\"\r\n",
    "    def solve1(self, n: int, limit: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(limit+1):\r\n",
    "            for j in range(limit+1):\r\n",
    "                k = n - i - j\r\n",
    "                if k >= 0 and k <= limit:\r\n",
    "                    ans += 1\r\n",
    "        return ans\r\n",
    "    \"\"\"\r\n",
    "        2. 排容原理\r\n",
    "        a. 所有方案數：\r\n",
    "            H(3, n) = C(n+2, n) = C(n+2, 2)\r\n",
    "        b. 至少一人拿到超過 limit 個糖果的方案數：\r\n",
    "            (先分(limit+1)給他，剩下的分給所有人)\r\n",
    "            3 * H(3, n-(limit+1)) = 3 * C(n−(limit+1)+2, 2)\r\n",
    "        c. 至少兩人拿到超過 limit 個糖果的方案數：\r\n",
    "            3 * C(n−2⋅(limit+1)+2, 2)\r\n",
    "    \"\"\"\r\n",
    "\r\n",
    "    def solve2(self, n: int, limit: int) -> int:\r\n",
    "        if n > 3 * limit: # 三人都拿到超過 limit 個糖果，沒有方案\r\n",
    "            return 0\r\n",
    "        ans = comb(n + 2, 2)\r\n",
    "        if n >= (limit + 1): # 至少一人拿到超過 limit 個糖果\r\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\r\n",
    "        if n >= 2 * (limit + 1): # 至少兩人拿到超過 limit 個糖果\r\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        dp = list()\n",
    "        for i in range(min(n + 1, limit + 1)):\n",
    "            dp.append(i + 1)\n",
    "        x = limit + 1\n",
    "        while n >= x and x <= 2 * limit:\n",
    "            dp.append(2 * limit - x + 1)\n",
    "            x += 1\n",
    "        ans = 0\n",
    "        # print(dp)\n",
    "        for i in range(min(n + 1, limit + 1)):\n",
    "            if n <= 2 * limit + i:\n",
    "                ans += dp[n - i]\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if 3 * limit < n:\n",
    "            return 0\n",
    "        cnt = [0] * (n + 1)\n",
    "        for i in range(min(n, 2 * limit) + 1):\n",
    "            if i > limit:\n",
    "                cnt[i] = 2 * limit - i + 1\n",
    "            else:\n",
    "                cnt[i] = i + 1\n",
    "        return sum(cnt[i] for i in range(n + 1) if n - i <= limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        \n",
    "#         @lru_cache(None)\n",
    "#         def dfs(i,j):\n",
    "#             if (3 - i) * limit < j:return 0\n",
    "#             if j == 0:return 1\n",
    "#             if i == 1:return max(0,min(limit,j) - max(0,(j - limit)) + 1)\n",
    "#             if i == 2:return j <= limit\n",
    "#             ans = 0\n",
    "#             for k in range(limit+1):\n",
    "#                 if k > j:break\n",
    "#                 ans += dfs(i+1,j-k)\n",
    "#             return ans\n",
    "        \n",
    "#         return dfs(0,n)\n",
    "    \n",
    "        dp = [[0 for _ in range(n+2)] for _ in range(5)]\n",
    "        for i in range(5):\n",
    "            dp[i][0] = 1\n",
    "        ans = 0\n",
    "        for j in range(max(0,n-limit),n+1):\n",
    "            if 2 * limit < j:\n",
    "                dp[1][j] = 0\n",
    "                break\n",
    "            # dp[1][j] = max(0,min(limit,j) - max(0,(j-limit)) + 1)\n",
    "            ans += max(0,min(limit,j) - max(0,(j-limit)) + 1)\n",
    "        return ans\n",
    "\n",
    "        # ans = 0\n",
    "        # if n <= limit:\n",
    "        #     for k in range(n+1):\n",
    "        #         ans += dp[1][n-k]\n",
    "        # else:\n",
    "        #     for k in range(limit+1):\n",
    "        #         ans += dp[1][n-k]\n",
    "        # return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for k in range(8):\n",
    "            t = bin(k).count('1')\n",
    "            rem = n - (limit + 1) * t\n",
    "            if rem < 0:\n",
    "                continue\n",
    "            ans += pow(-1, t) * comb(rem + 2, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n*(n-1)//2 if n>1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n+2)-3*c2(n-limit+1)+3*c2(n-2*limit)-c2(n-3*limit-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if n > 3 * limit:\n",
    "            return 0\n",
    "        ans = comb(n + 2, 2)\n",
    "        if n > limit:\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\n",
    "        if n - 2 >= 2 * limit:\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if n > 3 * limit:\n",
    "            return 0\n",
    "        ans = comb(n + 2, 2)\n",
    "        if n > limit:\n",
    "            ans -= 3 * comb(n - limit + 1, 2)\n",
    "        if n - 2 >= 2 * limit:\n",
    "            ans += 3 * comb(n - 2 * limit, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "                return (math.comb(n + 2, 2) - (3 * math.comb(max(n - (limit + 1) + 2, 0), 2) \n",
    "                                       - 3 * math.comb(max(n - 2 * (limit + 1) + 2, 0), 2) \n",
    "                                       + math.comb(max(n - 3 * (limit + 1) + 2, 0), 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        def cal(a, b):\n",
    "            if a < b:\n",
    "                return 0\n",
    "            return comb(a, b)\n",
    "        \n",
    "        return cal(n + 2, 2) - 3 * cal(n - limit + 1, 2) + 3 * cal(n - 2 * limit, 2) - cal(n - 3 * limit - 1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        def c(n):\n",
    "            if n < 2:\n",
    "                return 0\n",
    "            return comb(n, 2)\n",
    "        return comb(n + 2, 2) - 3 * c(n - (limit + 1) + 2) + 3 * c(n - 2 * (limit + 1) + 2) - c(n - 3 * (limit + 1) + 2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        def c(n):\n",
    "            if n < 2:\n",
    "                return 0\n",
    "            return comb(n, 2)\n",
    "        return comb(n + 2, 2) - 3 * c(n - (limit + 1) + 2) + 3 * c(n - 2 * (limit + 1) + 2) - c(n - 3 * (limit + 1) + 2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def C2(n: int) -> int:\n",
    "    if n <= 1:\n",
    "        return 0\n",
    "    return n * (n - 1) // 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        res0 = C2(n + 2)  # 总方案数,x1+x2+x3=n的非负整数解的个数(隔板法)\n",
    "        res1 = 3 * C2(n + 2 - (limit + 1))  # 至少一个小朋友分到的糖果超过 limit 的方案数\n",
    "        res2 = 3 * C2(n + 2 - 2 * (limit + 1))  # 至少两个小朋友分到的糖果超过 limit\n",
    "        res3 = C2(n + 2 - 3 * (limit + 1))  # 三个小朋友分到的糖果都超过 limit\n",
    "        return res0 - res1 + res2 - res3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        ans = 0\n",
    "        for k in range(8):\n",
    "            t = k.bit_count()\n",
    "            rem = n - (limit + 1) * t\n",
    "            if rem >= 0:\n",
    "                ans += pow(-1, t) * comb(rem + 2, 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "            \n",
    "        def helper(num):\n",
    "            if num < 0:\n",
    "                return 0\n",
    "            return (num + 2) * (num + 1) // 2\n",
    "\n",
    "        return helper(n) - (3 * helper(n - limit - 1) - 3 * helper(n - 2 * limit - 2) + helper(n - 3 * limit - 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def c2(n: int) -> int:\n",
    "#     return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, n: int, limit: int) -> int:\n",
    "#         print(c2(n + 2), c2(n - limit + 1), 3 * c2(n - 2 * limit), c2(n - 3 * limit - 1))\n",
    "#         return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, lim: int) -> int:\n",
    "        \n",
    "        co = math.comb \n",
    "        # def co(n, y) -> int:\n",
    "        #     return n * (n - 1) // 2 if n > 1 else 0\n",
    "        all = co(n + 3 - 1, 2) \n",
    "        if n<=lim:\n",
    "            a = 0 \n",
    "        else:\n",
    "            res = (n - 1 - lim) \n",
    "            a = co(res + 3 - 1, 2)\n",
    "        b = a \n",
    "        c = a \n",
    "        if n<(2*lim + 2):\n",
    "            d = 0 \n",
    "        else:\n",
    "            res = n-2-2*lim \n",
    "            d = co(res + 3 - 1, 2) \n",
    "        e = d \n",
    "        f = d \n",
    "        if n<(3*lim + 3):\n",
    "            g = 0 \n",
    "        else:\n",
    "            res = n-3-3*lim \n",
    "            g = co(res+3-1, 2) \n",
    "        # print(all, a, d, g)\n",
    "        return all - (a+b+c-d-e-f+g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        if n > limit*3: return 0\n",
    "        hi = n-max(0,n-2*limit)\n",
    "        lo = max(0,n-limit)\n",
    "        def calc(x):\n",
    "            return min(limit,x)-max(0,x-limit)+1\n",
    "        def calc2(mi,mx):\n",
    "            return (mi+mx)*(mx-mi+1)//2\n",
    "        # print(lo,hi)\n",
    "        if hi <= limit:\n",
    "            return calc2(calc(lo),calc(hi))\n",
    "        elif lo >= limit:\n",
    "            return calc2(calc(hi),calc(lo))\n",
    "        else:\n",
    "            return calc2(calc(lo),calc(limit))+calc2(calc(hi),calc(limit))-limit-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def c2(n: int) -> int:\n",
    "    return n * (n - 1) // 2 if n > 1 else 0\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(x):\n",
    "    if x <= 1:\n",
    "        return 0\n",
    "    return x*(x-1)//2\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, n: int, limit: int) -> int:\n",
    "        return check(n+2) - 3*check(n-limit+1) + 3*check(n-2*limit) - check(n-3*limit-1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans=[0 for i in range(num_people)]\n",
    "        i=0\n",
    "        while candies>0:\n",
    "            ans[i%num_people]=ans[i%num_people]+min(i+1,candies)\n",
    "            i+=1\n",
    "            candies=max(0,candies-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        res = [0] * num_people\n",
    "        index = 0\n",
    "        while candies:\n",
    "            people = index % num_people\n",
    "            cadit = index + 1\n",
    "            if candies >= cadit:\n",
    "                res[people] += cadit\n",
    "                candies -= cadit\n",
    "            else:\n",
    "                res[people] += candies\n",
    "                candies = 0\n",
    "            index += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        kids = [0]*num_people\n",
    "        i = 0\n",
    "        while candies>0:\n",
    "            kids[i%num_people] += min(i+1,candies)\n",
    "            candies -= i +1\n",
    "            i+=1\n",
    "        return kids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        total = 0\n",
    "        index = 1\n",
    "        ls = [0] * num_people\n",
    "        while total < candies:\n",
    "            _index = index % num_people - 1\n",
    "            if total + index > candies:\n",
    "                ls[_index] += candies - total\n",
    "            else:\n",
    "                ls[_index] += index\n",
    "            total += index\n",
    "            index += 1\n",
    "\n",
    "        return ls\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n = num_people\n",
    "        m = int((sqrt(8 * candies + 1) - 1) / (2 * n))\n",
    "        nm = n * m\n",
    "        answer = [(1+i) * m + nm * (m-1) // 2 for i in range(n)]\n",
    "        candies -= (1 + nm) * nm // 2\n",
    "        i = 0\n",
    "        while candies > 0:\n",
    "            c = min(nm + 1 + i, candies)\n",
    "            answer[i] += c\n",
    "            candies -= c\n",
    "            i = (i+1) % n\n",
    "        return answer\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        nums=[0]*num_people\n",
    "        con=0\n",
    "        cur=0\n",
    "        i=0\n",
    "        while con<candies:\n",
    "            if con+cur+1>candies:\n",
    "                nums[i]+=candies-con\n",
    "            else:\n",
    "                nums[i]+=cur+1\n",
    "            con+=cur+1\n",
    "            cur+=1\n",
    "            i+=1\n",
    "            i%=num_people\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        tmp = [0 for i in range(num_people)]\n",
    "        sum = 1\n",
    "        while candies:\n",
    "            for n in range(num_people):\n",
    "                if candies >=sum:\n",
    "                    tmp[n]+=sum\n",
    "                    candies-=sum\n",
    "                    sum+=1\n",
    "                else:\n",
    "                    tmp[n]+=candies\n",
    "                    candies = 0\n",
    "                    break\n",
    "        return tmp\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans=[0]*num_people\n",
    "        i=0\n",
    "        while candies:\n",
    "            if candies-(i+1)>=0:\n",
    "                ans[i%num_people]+=i+1\n",
    "                candies-=i+1\n",
    "            else:\n",
    "                ans[i%num_people]+=candies\n",
    "                candies=0\n",
    "            i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        list_,a,b=[0 for _ in range(num_people)],0,0\n",
    "        while True:\n",
    "            b+=1\n",
    "            if candies>=b:\n",
    "                list_[a]+=b\n",
    "            else:\n",
    "                b=candies\n",
    "                list_[a]+=b\n",
    "            candies-=b\n",
    "            a+=1\n",
    "            if candies==0:\n",
    "                return list_\n",
    "            if a==num_people:\n",
    "                a=0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         ans=[0]*num_people\n",
    "#         i=0\n",
    "#         while candies:\n",
    "#             if candies-(i+1)>=0:\n",
    "#                 ans[i%num_people]+=i+1\n",
    "#                 candies-=i+1\n",
    "#             else:\n",
    "#                 ans[i%num_people]+=candies\n",
    "#                 candies=0\n",
    "#             i+=1\n",
    "#         return ans\n",
    "\n",
    "# ### 官1：暴力\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         ans = [0] * num_people\n",
    "#         i = 0\n",
    "#         while candies != 0:\n",
    "#             ans[i % num_people] += min(i + 1, candies)\n",
    "#             candies -= min(i + 1, candies)\n",
    "#             i += 1\n",
    "#         return ans\n",
    "\n",
    "##官2：等差数列\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n = num_people\n",
    "        # how many people received complete gifts\n",
    "        p = int((2 * candies + 0.25)**0.5 - 0.5) \n",
    "        remaining = int(candies - (p + 1) * p * 0.5)\n",
    "        rows, cols = p // n, p % n\n",
    "        \n",
    "        d = [0] * n\n",
    "        for i in range(n):\n",
    "            # complete rows\n",
    "            d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n\n",
    "            # cols in the last row\n",
    "            if i < cols:\n",
    "                d[i] += i + 1 + rows * n\n",
    "        # remaining candies        \n",
    "        d[cols] += remaining\n",
    "        return d\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        full_groups=int(sqrt(2*candies+0.25)-0.5)\n",
    "        remain=candies-full_groups*(full_groups+1)//2\n",
    "        round=full_groups//num_people\n",
    "        round_candy_base=round+round*(round-1)//2*num_people\n",
    "        result=[round_candy_base+x*round for x in range(num_people)]\n",
    "        full_groups=full_groups%num_people\n",
    "        for i in range(full_groups):\n",
    "            result[i]+=round*num_people+1+i\n",
    "        result[full_groups]+=remain\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candyNum = [0] * num_people\n",
    "        n = 0\n",
    "        while True:\n",
    "            i = n % num_people\n",
    "            candyNum[i] += min(n + 1, candies)\n",
    "            n += 1\n",
    "            candies -= n\n",
    "            if candies <= 0 or candyNum[-1] == 2 * num_people:\n",
    "                break\n",
    "\n",
    "        return candyNum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        res = [0] * num_people\n",
    "        i = 0\n",
    "        while candies > 0:\n",
    "            res[i%num_people] += min(candies, i+1)\n",
    "            candies -= min(candies, i+1)\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         ans=[0]*num_people\n",
    "#         i=0\n",
    "#         while candies:\n",
    "#             if candies-(i+1)>=0:\n",
    "#                 ans[i%num_people]+=i+1\n",
    "#                 candies-=i+1\n",
    "#             else:\n",
    "#                 ans[i%num_people]+=candies\n",
    "#                 candies=0\n",
    "#             i+=1\n",
    "#         return ans\n",
    "\n",
    "# ### 官1：暴力\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        i = 0\n",
    "        while candies != 0:\n",
    "            ans[i % num_people] += min(i + 1, candies)\n",
    "            candies -= min(i + 1, candies)\n",
    "            i += 1\n",
    "        return ans\n",
    "\n",
    "# ##官2：等差数列\n",
    "# class Solution:\n",
    "#     def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "#         n = num_people\n",
    "#         # how many people received complete gifts\n",
    "#         p = int((2 * candies + 0.25)**0.5 - 0.5) \n",
    "#         remaining = int(candies - (p + 1) * p * 0.5)\n",
    "#         rows, cols = p // n, p % n\n",
    "        \n",
    "#         d = [0] * n\n",
    "#         for i in range(n):\n",
    "#             # complete rows\n",
    "#             d[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n\n",
    "#             # cols in the last row\n",
    "#             if i < cols:\n",
    "#                 d[i] += i + 1 + rows * n\n",
    "#         # remaining candies        \n",
    "#         d[cols] += remaining\n",
    "#         return d\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        '(a1+an)n/2。'\n",
    "        'na1+n(n-1)d/2'\n",
    "        circulation = 0\n",
    "        for i in range(1, candies):\n",
    "            if i + i * (i - 1) / 2 >= candies:\n",
    "                circulation = i\n",
    "                break\n",
    "        print(\"circulation\", circulation)\n",
    "\n",
    "        ls = [0] * num_people\n",
    "        _max = 0\n",
    "        for i in range(1, circulation + 1):\n",
    "            print(\"i\", i)\n",
    "            index = i % num_people - 1\n",
    "            if _max + i > candies:\n",
    "                ls[index] += candies - _max\n",
    "                return ls\n",
    "            ls[index] += i\n",
    "            _max += i\n",
    "        return ls\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        tmp = [0]*num_people\n",
    "        sum = 1\n",
    "        while candies:\n",
    "            for n in range(num_people):\n",
    "                if candies >=sum:\n",
    "                    tmp[n]+=sum\n",
    "                    candies-=sum\n",
    "                    sum+=1\n",
    "                else:\n",
    "                    tmp[n]+=candies\n",
    "                    candies = 0\n",
    "                    break\n",
    "        return tmp\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        result=[0]*num_people\n",
    "        num=0\n",
    "        while candies>0:\n",
    "            for i in range(num_people):\n",
    "                num+=1\n",
    "                if num<=candies:\n",
    "                    result[i]+=num\n",
    "                    candies=candies-num\n",
    "                else:\n",
    "                    result[i]+=candies\n",
    "                    candies=0\n",
    "                    break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans=[0 for _ in range(num_people)]\n",
    "        n=1\n",
    "        while candies>0:\n",
    "            for i in range(num_people):\n",
    "                if candies>n:\n",
    "                    ans[i]=ans[i]+n\n",
    "                    candies=candies-n\n",
    "                    n+=1\n",
    "                else:\n",
    "                    ans[i]=ans[i]+candies\n",
    "                    candies=0\n",
    "            print(ans)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        nums = [0]*num_people\n",
    "        k = 1\n",
    "        # flage = 0\n",
    "        while candies!=0:\n",
    "            for i in range(num_people):\n",
    "                if candies >= k:\n",
    "                    nums[i] += k\n",
    "                    candies -= k\n",
    "                    k += 1\n",
    "                else:\n",
    "                    nums[i] += candies\n",
    "                    candies -= candies\n",
    "                    # flage = 1\n",
    "                    break\n",
    "            # if candies == 0:\n",
    "            #     break\n",
    "        print(nums)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        de = [0]*num_people\n",
    "        print(de)\n",
    "        s = 0\n",
    "        while s*(s+1) < 2*candies:\n",
    "            lun,duo = (s+1)//num_people,(s+1)%num_people\n",
    "            s += 1\n",
    "        print(lun,duo)\n",
    "        for i in range(lun):\n",
    "            for j in range(num_people):\n",
    "                de[j] += num_people*i+(j+1)\n",
    "        print(de)\n",
    "        if duo >= 1:\n",
    "            for i in range(duo-1):\n",
    "                de[i] += num_people*lun+(i+1)\n",
    "            re = int(candies - (lun*num_people+duo-1)*(lun*num_people+duo)/2)\n",
    "            de[duo-1] += re\n",
    "        else:\n",
    "            de[num_people-1] = int((lun-1)*(num_people*lun)/2)\n",
    "            re = int(candies - (lun*num_people+duo-1)*(lun*num_people+duo)/2)\n",
    "            de[num_people-1] += re\n",
    "        return de"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ls = []\n",
    "        ls_count = []\n",
    "        for i in range(1,100000):\n",
    "\n",
    "            if candies - sum(ls) < i:\n",
    "                ls.append(candies - sum(ls))\n",
    "                break\n",
    "            else:\n",
    "                ls.append(i)\n",
    "        for j in range(num_people):\n",
    "            ls_count.append(sum(ls[j::num_people]))\n",
    "        return ls_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        i = 1\n",
    "        res = []\n",
    "        while (1+i)*i//2 <= candies:\n",
    "            res.append(i)\n",
    "            i += 1\n",
    "        \n",
    "        if (i-1)*i//2 < candies:\n",
    "            res.append(candies-(i-1)*i//2)\n",
    "        \n",
    "        ans = [0]*num_people\n",
    "        for i in range(len(res)):\n",
    "            ans[i%num_people] += res[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        cand=[]\n",
    "        i=1\n",
    "        while candies>0:\n",
    "            if candies > i:\n",
    "                candies = candies - i\n",
    "                cand.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                cand.append(candies)\n",
    "                break\n",
    "        ans=[]\n",
    "        for i in range(len(cand)):\n",
    "            if len(ans)< num_people and i<=num_people:\n",
    "                ans.append(cand[i])\n",
    "            else:\n",
    "                ans[i%num_people]=cand[i]+ans[i%num_people]\n",
    "        if len(ans)==num_people:\n",
    "            return ans\n",
    "        else:\n",
    "            for i in range (len(ans),num_people):\n",
    "                ans.append(0)\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_list = []\n",
    "        i = 1\n",
    "        while candies > i:\n",
    "            candies_list.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        if  candies:\n",
    "            candies_list.append(candies)\n",
    "        ans = []\n",
    "        for  i in range(num_people):\n",
    "            ans.append(sum(candies_list[i::num_people]))\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        res = []\n",
    "        num = []\n",
    "        result = [0] * num_people\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            if candies >= i:\n",
    "                num.append(i)\n",
    "                candies -= i\n",
    "                if len(num) == num_people:\n",
    "                    res.append(num)\n",
    "                    num = []\n",
    "                if candies == 0:\n",
    "                    num += [0] * (num_people - len(num))\n",
    "                    res.append(num)\n",
    "                    break\n",
    "            else:\n",
    "                num.append(candies)\n",
    "                num += [0] * (num_people - len(num))\n",
    "                res.append(num)\n",
    "                break\n",
    "            i += 1\n",
    "        for k in range(num_people):\n",
    "            for j in range(len(res)):\n",
    "                result[k] += res[j][k]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        from collections import defaultdict\n",
    "        import logging\n",
    "        dic = defaultdict(int)\n",
    "        x=1\n",
    "        while candies>0:\n",
    "            for i in range(num_people):\n",
    "                if candies>x:\n",
    "                    dic[i]+=x\n",
    "                    candies-=x\n",
    "                else:\n",
    "                    dic[i]+=candies\n",
    "                    candies=0\n",
    "                    break\n",
    "                x+=1\n",
    "        result=[]\n",
    "        for i in range(num_people):\n",
    "            result.append(dic[i])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        candies_tmp = int((8*candies + 1)**0.5/2 - 0.5)\n",
    "        new_candies = list(range(1,candies_tmp+1))\n",
    "        new_candies.append(candies - sum(new_candies))\n",
    "        res = [0]*num_people\n",
    "        idx = 0\n",
    "        for i in new_candies:\n",
    "            res[idx%num_people] += i\n",
    "            idx += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        ans = [0] * num_people\n",
    "        n = int( math.sqrt(2 * candies))\n",
    "        r = candies - n * (n+1)//2\n",
    "        if r < 0:\n",
    "            n-=1\n",
    "            r = candies - n * (n+1)//2\n",
    "        l = list(range(1, n + 1))\n",
    "        if r > 0:\n",
    "            l.append(r)\n",
    "        for i, c in enumerate(l):\n",
    "            ans[i  % num_people ]+=c\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "                          i=1\n",
    "                          a=[]\n",
    "                          b=[0]*num_people                          \n",
    "                          while candies>0 :\n",
    "                             if candies-i>=0:\n",
    "                                a.append(i)\n",
    "                                candies=candies-i\n",
    "                                i=i+1\n",
    "                             else:\n",
    "                                 a.append(candies)\n",
    "                                 candies=candies-i\n",
    "                          for i in range(len(a)):\n",
    "                                 b[i%num_people]=b[i%num_people]+a[i]\n",
    "                          return b\n",
    "                               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        li = []\n",
    "        res = [0]*num_people\n",
    "        candy = 1\n",
    "        i = candies\n",
    "        while i >= candy:\n",
    "            li.append(candy)\n",
    "            i -= candy\n",
    "            candy += 1\n",
    "        li.append(i)\n",
    "        for i in range(len(li)):\n",
    "            a = i % num_people\n",
    "            res[a] += li[i]\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n_list = []\n",
    "        for i in range(1, candies):\n",
    "            if candies > i:\n",
    "                n_list.append(i)\n",
    "                candies -= i\n",
    "            else:\n",
    "                n_list.append(candies)\n",
    "                break\n",
    "        s_list = []\n",
    "        for i in range(num_people):\n",
    "            sum_n = 0\n",
    "            for j in range(i, len(n_list), num_people):\n",
    "                sum_n += n_list[j]\n",
    "            s_list.append(sum_n)\n",
    "        return s_list\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        out = list()\n",
    "\n",
    "        i = 1\n",
    "\n",
    "        while candies > 0:\n",
    "            a = min(candies,i)\n",
    "            out.append(a)\n",
    "\n",
    "            i += 1\n",
    "            candies -= a\n",
    "\n",
    "        output = [0 for i in range(num_people)]\n",
    "\n",
    "        for i in range(num_people):\n",
    "            for j in range(i,len(out),num_people):\n",
    "                output[i] += out[j]\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        result = []\n",
    "        n = 1\n",
    "        while candies > 0:\n",
    "            if n <= candies:\n",
    "                result.append(n)\n",
    "            else:\n",
    "                result.append(candies)\n",
    "            candies = candies - n\n",
    "            n += 1\n",
    "        use_l = len(result)\n",
    "        if use_l < num_people:\n",
    "            result = result + [0] * (num_people - use_l)\n",
    "        else:\n",
    "            for i in range(num_people):\n",
    "                result[i] = sum(result[i::num_people])\n",
    "            result = result[:num_people]\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "       i=0\n",
    "       sum = 0\n",
    "       ans=[]\n",
    "       while sum<=candies:\n",
    "           i+=1\n",
    "           ans.append(i)\n",
    "           sum+=i\n",
    "       m=candies-(sum-ans[-1])\n",
    "       ans.pop()\n",
    "       ans.append(m)\n",
    "       ans1=[0]*num_people\n",
    "       for i in range(0,len(ans)):\n",
    "           ans1[((i+1)%num_people)-1] += ans[i] \n",
    "       return ans1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int):\n",
    "        lst = [1]\n",
    "        res = []\n",
    "        for i in range(2, candies):\n",
    "            if sum(lst) + i < candies:\n",
    "                lst.append(i)\n",
    "            else:\n",
    "                lst.append(candies - sum(lst))\n",
    "                break\n",
    "        for i in range(num_people):\n",
    "            sums = 0\n",
    "            for j in range(i, len(lst), num_people):\n",
    "                sums += lst[j]\n",
    "            res.append(sums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        kids = [0] * num_people\n",
    "        dp = [1]\n",
    "        candies -= 1\n",
    "        while candies > 0:\n",
    "            curr = dp[-1] + 1\n",
    "            if candies >= curr:\n",
    "                candies -= curr\n",
    "                dp.append(curr)\n",
    "            else:\n",
    "                dp.append(candies)\n",
    "                candies = 0\n",
    "        for i in range(len(dp)):\n",
    "            kids[i%num_people] += dp[i]\n",
    "        return kids\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        a = 1\n",
    "        list1 = []\n",
    "        while candies>a:\n",
    "            list1.append(a)\n",
    "            candies-=a\n",
    "            a+=1\n",
    "        list1.append(candies)\n",
    "\n",
    "        list2 = []\n",
    "        for i in range(num_people):\n",
    "            list2.append(sum(list1[i::num_people]))\n",
    "        return list2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        l = []\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            l.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        l[-1] += candies\n",
    "        res = [0] * num_people\n",
    "        for i in range(num_people):\n",
    "            res[i] = sum(l[i::num_people])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        l = []\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            l.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        l[-1] += candies\n",
    "        res = [0] * num_people\n",
    "        for i in range(num_people):\n",
    "            res[i] = sum(l[i::num_people])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        l = []\n",
    "        i = 1\n",
    "        while candies > 0:\n",
    "            l.append(i)\n",
    "            candies -= i\n",
    "            i += 1\n",
    "        l[-1] += candies\n",
    "        res = [0] * num_people\n",
    "        for i in range(num_people):\n",
    "            res[i] = sum(l[i::num_people])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        for i in range(int((2*candies)**0.5)+2,-1,-1):\n",
    "            if i*(i+1)//2 <=candies<=(i+1)*(i+2)//2:\n",
    "                s = i\n",
    "        b = candies-s*(s+1)//2\n",
    "        num = [i for i in range(1,s+1)] +[b]\n",
    "        result = [0]*num_people\n",
    "        for j in range(len(num)):\n",
    "            m = j%num_people\n",
    "            result[m] += num[j]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n = 1\n",
    "        while n * (n + 1) / 2 < candies:\n",
    "            n += 1\n",
    "        candies_lst = [i for i in range(1, n)] + [candies - n * (n - 1) // 2]\n",
    "        res = []\n",
    "        for i in range(num_people):\n",
    "            res.append(sum(candies_lst[i::num_people]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        arr_can = []\n",
    "        # the candies num we give to every person\n",
    "        use_can = 1\n",
    "        # remain candies\n",
    "        re_can = candies\n",
    "        # result\n",
    "        res = [0] * num_people\n",
    "        while re_can > use_can:\n",
    "            # when we have candies to give\n",
    "            re_can = re_can - use_can\n",
    "            arr_can.append(use_can)\n",
    "            use_can += 1\n",
    "            # debug cmd\n",
    "        # last person receive all remaining candies\n",
    "        arr_can.append(re_can)\n",
    "        # debug cmd\n",
    "        print(arr_can)\n",
    "        num_give = int(len(arr_can)/num_people) + 1\n",
    "        # compute the complete give candies two-dimensional array\n",
    "        all_give = num_give * num_people\n",
    "        arr_can = arr_can + [0] * (all_give - len(arr_can))\n",
    "        # compute the candies that every person receive\n",
    "        for i in range(num_people):\n",
    "            # the turn we give candies, start from 0\n",
    "            give = 0\n",
    "            while give < num_give:\n",
    "                res[i] += arr_can[i+give*num_people]\n",
    "                give += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        data = []\n",
    "        for i in range(1,candies):\n",
    "            data.append(i)\n",
    "            if sum(data)> candies:\n",
    "                data.pop()\n",
    "                break\n",
    "        last = candies - sum(data)\n",
    "        data.append(last)\n",
    "        print('last:',data)\n",
    "        group = []\n",
    "        for i in range(0,len(data),num_people):\n",
    "            group.append(data[i:i+num_people])\n",
    "        if len(group[-1]) != num_people:\n",
    "            for i in range(num_people - len(group[-1])):\n",
    "                group[-1].append(0)\n",
    "        result = []\n",
    "        for i in list(zip(*group)):\n",
    "            result.append(sum(i))\n",
    "        return result \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        n=0\n",
    "        while n*(n+1)/2<candies:\n",
    "            n+=1\n",
    "        res=[0]*n\n",
    "        for i in range(n-1):\n",
    "            res[i]=i+1\n",
    "        res[n-1]=int(candies-(n-1)*n/2)\n",
    "        result=[0]*num_people\n",
    "        print(res)\n",
    "        for i,value in enumerate(res):\n",
    "            index=i\n",
    "            while index >=num_people:\n",
    "                index-=num_people\n",
    "            result[index]+=value\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        i = 0\n",
    "        #计算有多少个元素\n",
    "        while True:\n",
    "            tmp = i ** 2 + i\n",
    "            if tmp >= 2 * candies:\n",
    "                break\n",
    "            i += 1\n",
    "        m, n = divmod(i, num_people)#有n+1行，最后剩n个元素，如果n不为0，则有m + 2行\n",
    "        if n != 0:\n",
    "            m += 1\n",
    "        li_w = []\n",
    "        total = 0\n",
    "        for k in range(m):\n",
    "            li = []\n",
    "            for j in range(num_people):\n",
    "                total += num_people*k + 1 + j\n",
    "                if total >= candies:\n",
    "                    li.append(num_people*k + 1 + j + candies - total)\n",
    "                    if j < num_people - 1:\n",
    "                        for k in range(num_people - 1 - j):\n",
    "                            li.append(0)\n",
    "                    break\n",
    "                else:\n",
    "                    li.append(num_people*k + 1 + j)\n",
    "            li_w.append(li)\n",
    "        li_t = [0]*num_people\n",
    "\n",
    "        for x in range(num_people):\n",
    "            tmp = 0\n",
    "            for y in range(m):\n",
    "                tmp += li_w[y][x]\n",
    "            li_t[x] = tmp\n",
    "\n",
    "        return li_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        list_candy = []\n",
    "        candy_consum = 1\n",
    "        outcome = []\n",
    "        while candies - candy_consum > 0:\n",
    "            list_candy.append(candy_consum)\n",
    "            candies -= candy_consum\n",
    "            candy_consum += 1\n",
    "        list_candy.append(candies)\n",
    "        times = len(list_candy)/num_people\n",
    "        for i in range(num_people):\n",
    "            outcome.append(0)\n",
    "        if int(times) != times:\n",
    "            times = int(times) + 1\n",
    "        else:\n",
    "            times = int(times)\n",
    "        for i in range(times):\n",
    "            for j in range(num_people):\n",
    "                if i * num_people + j <= len(list_candy) - 1:\n",
    "                    outcome[j] += list_candy[i*num_people+j]\n",
    "                else: break\n",
    "        return outcome\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        sum1 = 0\n",
    "        ans, res = [], [0 for _ in range(num_people)]\n",
    "\n",
    "        for i in range(1, candies):\n",
    "            sum1 += i\n",
    "  \n",
    "            if sum1 >= candies:\n",
    "                ans.append(candies - sum1 + i)\n",
    "            else:\n",
    "                ans.append(i)\n",
    "\n",
    "            res[(i - 1) % num_people] += ans[i - 1]\n",
    "            \n",
    "            if sum1 >= candies:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        sum1 = 0\n",
    "        ans, res = [], [0 for _ in range(num_people)]\n",
    "\n",
    "        for i in range(1, candies):\n",
    "            sum1 += i\n",
    "  \n",
    "            if sum1 >= candies:\n",
    "                ans.append(candies - sum1 + i)\n",
    "            else:\n",
    "                ans.append(i)\n",
    "\n",
    "            res[(i - 1) % num_people] += ans[i - 1]\n",
    "            \n",
    "            if sum1 >= candies:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        allocate = []\n",
    "        cnt = 1\n",
    "        sums = 1\n",
    "        while sums <= candies:\n",
    "            allocate.append(cnt)            \n",
    "            cnt += 1\n",
    "            sums += cnt\n",
    "        allocate.append(cnt + candies - sums)\n",
    "        res = [0] * num_people\n",
    "        for i in range(len(allocate)):\n",
    "            res[i % num_people] += allocate[i]\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "\n",
    "        sum1 = 0\n",
    "        ans, res = [], [0 for _ in range(num_people)]\n",
    "\n",
    "        for i in range(1, candies):\n",
    "            sum1 += i\n",
    "  \n",
    "            if sum1 >= candies:\n",
    "                ans.append(candies - sum1 + i)\n",
    "            else:\n",
    "                ans.append(i)\n",
    "\n",
    "            res[(i - 1) % num_people] += ans[i - 1]\n",
    "            \n",
    "            if sum1 >= candies:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
